Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.
A string s is said to be one distance apart from a string t if you can:
- Insert exactly one character into
sto gett. - Delete exactly one character from
sto gett. - Replace exactly one character of
swith a different character to gett.
Example 1:
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "a", t = "" Output: true
Example 4:
Input: s = "", t = "A" Output: true
Constraints:
0 <= s.length <= 1040 <= t.length <= 104sandtconsist of lower-case letters, upper-case letters and/or digits.
Average Rating: 4.56 (36 votes)
Solution
Approach 1: One pass algorithm
Intuition
First of all, let's ensure that the string lengths are not too far from each
other. If the length difference is 2 or more characters, then s and t couldn't be
one edit away strings.
For the next let's assume that s is always shorter or the same length as t.
If not, one could always call isOneEditDistance(t, s) to inverse the string order.
Now it's time to pass along the strings and to look for the first different character.
If there is no differences between the first len(s) characters,
only two situations are possible :
-
The strings are equal.
-
The strings are one edit away distance.
Now what if there is a different character so that s[i] != t[i].
-
If the strings are of the same length, all next characters should be equal to keep one edit away distance. To verify it, one has to compare the substrings of
sandtboth starting from thei + 1th character. -
If
tis one character longer thans, the additional charactert[i]should be the only difference between both strings. To verify it, one has to compare a substring ofsstarting from theith character and a substring oftstarting from thei + 1th character.
Implementation
Complexity Analysis
-
Time complexity : O(N) in the worst case when string lengths are close enough
abs(ns - nt) <= 1, whereNis a number of characters in the longest string. O(1) in the best case whenabs(ns - nt) > 1. -
Space complexity : O(N) because strings are immutable in Python and Java and to create substring costs O(N) space.
Problem generalization : Edit distance
June 30, 2019 11:19 PM
This solution is not O(1) memory, each s.substring will create a new string object.
March 25, 2020 7:40 AM
Logic is like this
- Get the length of both s & t strings as l1 and l2
- If they differ more than 1, they are more than one edit distance apart, so straight return false.
- Have two pointers i and j, starting with 0th index in s & t strings respectively and loop until they are same.
- Now we are at a point where both chars pointed by i and j are different or we reach end of both strings.
- If we reach end of both strings, it means both strings are same, so straight return false as same strings cannot be one edit distance apart.
- If l1 > l2, which means s is longer than t, so only deletion is possible. Ignore the current character s[i], and see if remaining of s[i+1, l1] matches with t[j, l2]. If matches they are one edit distance apart, else no.
- If l1 < l2, which means s is shorter than t, so only insertion is possible. Assuming we insert t[j] at ith index in s and see if remaining of s[i, l1] matches with t[j+1, l2]. If matches they are one edit distance apart, else no.
- If l1 == l2, which means s and t are of same length, so only replacing is possible. Assuming we replace s[i] with t[j] and see if remaining of s[i+1, l1] matches with t[j+1, l2]. If matches they are one edit distance apart, else no.
class Solution {
public boolean isOneEditDistance(String s, String t) {
int l1 = s.length();
int l2 = t.length();
if (Math.abs(l1 - l2) > 1) {
// more than 1 edit distance apart
return false;
}
int i = 0;
int j = 0;
while (i < l1 && j < l2 && s.charAt(i) == t.charAt(j)) {
i++;
j++;
}
if (i == l1 && j == l2) {
return false;
}
if (l1 > l2) {
// deletion is only possible
return s.substring(i + 1).equals(t.substring(j));
} else if (l1 < l2) {
// insertion is only possible
return s.substring(i).equals(t.substring(j + 1));
} else {
// replacing is only possible
return s.substring(i + 1).equals(t.substring(j + 1));
}
}
}
My 2 pointer approach:
Time complexity: O(max(m,n))
Space complexity: O(1)
class Solution(object):
def isOneEditDistance(self, s, t):
if abs(len(s) - len(t)) > 1 or s == t:
return False
found_inequality = False
i = j = 0
while i < len(s) and j < len(t):
if s[i] != t[j]:
if found_inequality: return False
found_inequality = True
if len(s) < len(t): i -= 1
elif len(s) > len(t): j -= 1
i += 1
j += 1
return True
We can use two pointers, instead of substrings to make it O(1) space.
I would say that identical strings should return true. I hate it when these problems aren't fully specified.
Why output should be false when input is "c" and "c"? It didn't say u cannot use the same character to replace the old one, so why i cannot use a letter "c" to replace itself?
Correct me if I am wrong but since a substring is created in the approach 1, this algo is O(N) space too since in Java, C# strings are immutable.
October 22, 2019 1:22 PM
A very straightforward and easy to understand solution, of course the code can be compressed by adding some better if..else, but it is still fairly fast.
Runtime: 1 ms, faster than 99.67% of Java online submissions for One Edit Distance.
Memory Usage: 38 MB, less than 85.29% of Java online submissions for One Edit Distance.
class Solution {
public boolean isOneEditDistance(String s, String t) {
int lenDiff = s.length() - t.length();
if(lenDiff > 1 || lenDiff < -1)
{
return false;
}
int distance = 0;
if(lenDiff == 1) //removal case; s>t
{
if(t == null || t.isEmpty())
return true;
distance = s.length();
int j = 0;
for(int i=0; i<s.length(); i++)
{
if(s.charAt(i) == t.charAt(j))
{
distance--;
j++;
if(j >= t.length())
break;
}
}
}
else if(lenDiff == -1) //insertion case; t>s
{
if(s == null || s.isEmpty())
return true;
distance = t.length();
int j = 0;
for(int i=0; i<t.length(); i++)
{
if(t.charAt(i) == s.charAt(j))
{
distance--;
j++;
if(j >= s.length())
break;
}
}
}
else if(lenDiff == 0) //replacement case; s==t
{
if(t == null || t.isEmpty())
return false;
distance=s.length();
for(int i=0; i<s.length(); i++)
{
if(t.charAt(i) == s.charAt(i))
distance--;
}
}
if(distance == 1)
return true;
else
return false;
}
}
August 5, 2019 8:14 AM
return true works fine for me. Curious to know when (ns + 1 == nt) will be executed?
In any, match or not-match case, it should be already returned in the for loop, AFAIK.
if (Math.abs(s.length() - t.length()) > 1)
return false;
int countChanges = 0;
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length ; i++){
if(arr[i] != t.charAt(i)){
countChanges++;
}
if(countChanges > 1){
break;
}
}
if(countChanges <= 1){
return true;
}
return false;
} ```Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/07/2021 11:55 | Accepted | 8 ms | 6.7 MB | cpp |
xxxxxxxxxxclass Solution {public: bool isOneEditDistance(string s, string t) { int m = s.size(), n = t.size(); if (m > n) { return isOneEditDistance(t, s); } for (int i = 0; i < m; i++) { if (s[i] != t[i]) { if (m == n) { return s.substr(i + 1) == t.substr(i + 1); } return s.substr(i) == t.substr(i + 1); } } return m + 1 == n; }};

